﻿#include "CirLinkList.h"
#include <iostream>
using namespace std;

//在第i个位置（位置编号从1开始）插入指定元素e
template <typename T>
bool CirLinkList<T>::ListInsert(int i, const T& e)
{
	//判断插入位置i是否合法，i的合法值应该是1到length+1之间
	if (i < 1 || i >(_length + 1))
	{
		cout << "元素" << e << "插入的位置" << i << "不合法，合法的位置是1到" << _length + 1 << "之间!" << endl;
		return false;
	}

	Node<T>* p = _head;

	//整个for循环用于找到第i-1个节点
	for (int j = 0; j < (i - 1); ++j)//j从0开始，表示p刚开始指向的是第0个节点（头结点）
	{
		p = p->next; //p会找到当前要插入的位置，比如要在第2个位置插入，p会指向第1个位置(节点)
	}

	Node<T>* newNode = new Node<T>;
	newNode->data = e;
	newNode->next = p->next;//让新节点链上后续链表，因为p->next指向后续的链表节点
	p->next = newNode;//让当前位置链上新节点，因为newNode指向新节点

	cout << "成功在位置为" << i << "处插入元素" << e << "!" << endl;
	_length++;	        //实际表长+1
	return true;
}


//删除第i个位置的元素
template < typename T>
bool CirLinkList<T>::ListDelete(int i)
{
	if (_length < 1)
	{
		cout << "当前单循环链表为空，不能删除任何数据!" << endl;
		return false;
	}
	if (i < 1 || i > _length)
	{
		cout << "删除的位置" << i << "不合法，合法的位置是1到" << _length << "之间!" << endl;
		return false;
	}

	Node<T>* p = _head;

	//整个for循环用于找到第i-1个节点
	for (int j = 0; j < (i - 1); ++j)//j从0开始，表示p刚开始指向的是第0个节点（头结点）
	{
		p = p->next; //p会找到当前要删除的位置所代表的节点的前一个节点的位置，比如要删除第2个位置的节点，p会指向第1个位置(节点)
	}

	Node<T>* delNode = p->next; //delNode指向待删除的节点
	p->next = delNode->next; //第i-1个节点的next指针指向第i+1个节点
	cout << "成功删除位置为" << i << "的元素，该元素的值为" << delNode->data << "!" << endl;
	_length--;       //实际表长-1
	delete delNode;
	return true;
}

//获得第i个位置的元素值
template<class T>
bool CirLinkList<T>::GetElem(int i, T& e)
{
	if (_length < 1)
	{
		cout << "当前单循环链表为空，不能获取任何数据!" << endl;
		return false;
	}

	if (i < 1 || i > _length)
	{
		cout << "获取元素的位置" << i << "不合法，合法的位置是1到" << _length << "之间!" << endl;
		return false;
	}

	Node<T>* p = _head;
	for (int j = 0; j < i; ++j)
	{
		p = p->next;
	}
	e = p->data;
	cout << "成功获取位置为" << i << "的元素，该元素的值为" << e << "!" << endl;
	return true;
}

//按元素值查找其在单循环链表中第一次出现的位置
template<class T>
int CirLinkList<T>::LocateElem(const T& e)
{
	Node<T>* p = _head;
	for (int i = 1; i <= _length; ++i)
	{
		if (p->next->data == e)
		{
			cout << "值为" << e << "的元素在单循环链表中第一次出现的位置为" << i << "!" << endl;
			return i;
		}
		p = p->next;
	}
	cout << "值为" << e << "的元素在单循环链表中没有找到!" << endl;
	return -1;  //返回-1表示查找失败
}

//输出单循环链表中的所有元素，时间复杂度为O(n)
template<class T>
void CirLinkList<T>::DispList()
{
	Node<T>* p = _head->next;
	while (p != _head) //这里采用while循环或者for循环书写都可以
	{
		cout << p->data << " ";  //每个数据之间以空格分隔
		p = p->next;
	}
	cout << endl; //换行
}

//获取单循环链表的长度，时间复杂度为O(1)
template<class T>
int  CirLinkList<T>::ListLength()
{
	return _length;
}

//判断单循环链表是否为空，时间复杂度为O(1)
template<class T>
bool CirLinkList<T>::Empty()
{
	if (_head->next == _head) //单循环链表为空
	{
		return true;
	}
	return false;
}






